package com.lw.leetcode.back.b;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * back
 * 1718. 构建字典序最大的可行序列
 *
 * @author liw
 * @version 1.0
 * @date 2022/4/25 14:17
 */
public class ConstructDistancedSequence {


    public static void main(String[] args) {
        ConstructDistancedSequence test = new ConstructDistancedSequence();

        // [8,6,4,2,7,2,4,6,8,5,3,7,1,3,5]
//        int n = 2;

        // [8,6,4,2,7,2,4,6,8,5,3,7,1,3,5]
//        int n = 8;

        //[9,7,5,3,8,6,3,5,7,9,4,6,8,2,4,2,1]
//        int n = 9;

        //[11,9,10,6,4,1,7,8,4,6,9,11,10,7,5,8,2,3,2,5,3]
//        int n = 11;

        //[11,9,10,6,4,1,7,8,4,6,9,11,10,7,5,8,2,3,2,5,3]
        int n = 20;

        int[] ints = test.constructDistancedSequence(n);
        System.out.println(Arrays.toString(ints));
    }

    private int[] arr;
    private int[] items;
    private int n;
    private int length;

    public int[] constructDistancedSequence(int n) {
        length = (n << 1) - 1;
        arr = new int[n];
        items = new int[length];
        this.n = n;
        find(0);
        return items;
    }

    private boolean find(int index) {
        if (index == length) {
            return true;
        }
        if (items[index] != 0) {
            return find(index + 1);
        }
        for (int i = n - 1; i >= 0; i--) {
            if (arr[i] == 0) {
                if (i == 0) {
                    arr[0] = 1;
                    items[index] = 1;
                    if (find(index + 1)) {
                        return true;
                    }
                    arr[0] = 0;
                    items[index] = 0;
                } else if (index + i + 1 < length && items[index + i + 1] == 0) {
                    arr[i] = 1;
                    items[index] = i + 1;
                    items[index + i + 1] = i + 1;
                    if (find(index + 1)) {
                        return true;
                    }
                    arr[i] = 0;
                    items[index] = 0;
                    items[index + i + 1] = 0;
                }
            }
        }
        return false;
    }


}
